package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

import java.util.HashMap;
import java.util.LinkedList;

public class ConstructBinaryTreeFromInorderAndPostorderTraversal {

    /**
     * 中序遍历就是先中序遍历左子树，然后再依次中序遍历根节点和右子树，所以找到根节点，左边的元素都是左子树，右边的元素都是右子树
     * 后序遍历就是先后序遍历左节点，然后后序遍历右节点，最终遍历根节点
     * 因此我们可以按后序遍历的逆顺序来找到根节点， 然后通过递归来构建树,
     * 又因为先找到的节点除根节点外是属于右子树的节点，所以优先构建右子树
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int m = inorder.length;
        LinkedList<Integer> deque = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int j = 0; j < m; ++j){
            map.put(inorder[j], j);
        }
        for (int i = m - 1; i >= 0; --i){
            deque.add(map.get(postorder[i]));
        }
        System.out.println(deque);
        return buildTree(inorder, deque, 0, m - 1);
    }

    public TreeNode buildTree(int[] inorder, LinkedList<Integer> deque, int inorderBegin, int inorderEnd){
        if (deque.isEmpty()){
            return null;
        }
        if (inorderBegin > inorderEnd){
            return null;
        }
        int index = deque.poll();
        int val = inorder[index];
        TreeNode root = new TreeNode(val);
        root.right = buildTree(inorder, deque, index + 1, inorderEnd);
        root.left = buildTree(inorder, deque, inorderBegin, index - 1);
        return root;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        TreeNode tree = new ConstructBinaryTreeFromInorderAndPostorderTraversal().buildTree(inorder, postorder);
        System.out.println();
        PrintUtils.println(tree);
    }
}
